﻿#include <iostream>
#include "LinkedListNode.h"

// 空间复杂度O(1)实现
static bool isPalindrome(LinkedListNode* head)
{
    // 快指针, 步进2
    auto fast = head;
    // 慢指针, 步进1
    auto slow = head;
    size_t nodeCount = 0;
    auto cur = head;
    while (cur)
    {
        ++nodeCount;
        cur = cur->next;
    }

    if (nodeCount == 1) return true;

    if (nodeCount == 2)
    {
        return head->value == head->next->value;
    }

    while (fast)
    {
        if (fast->next && fast->next->next)
        {
            fast = fast->next->next;
        }
        else
        {
            break;
        }

        slow = slow->next;
    }

    bool bPalindrome = true;
    auto halfEnd = slow;
    auto halfStart = slow->next;
    slow->next = nullptr;
    cur = halfStart;
    auto r = reverseLinkedList(head);
    if (nodeCount % 2 == 1)
    {
        r = r->next;
    }

    while (cur && r)
    {
        if (cur->value != r->value)
        {
            bPalindrome = false;
            break;
        }

        cur = cur->next;
        r = r->next;
    }

    reverseLinkedList(halfEnd);
    halfEnd->next = halfStart;

    return bPalindrome;
}

//  判断一个链表是否为回文结构
// [题目] 给定一个单链表的头节点head，请判断该链表是否为回文结构。
// [例子] 1->2->1, 返回true; 1->2->2->1, 返回true; 15->6->15, 返回true; 1->2->3, 返回false。
// 如果链表长度为N，时间复杂度达到O(N), 额外空间复杂度达到O(1)
int main_Palindrome_LinkedList()
{
    auto head = new LinkedListNode(1);
    head->next = new LinkedListNode(2);
    head->next->next = new LinkedListNode(3);
    head->next->next->next = new LinkedListNode(3);
    head->next->next->next->next = new LinkedListNode(2);
    head->next->next->next->next->next = new LinkedListNode(1);

    printLinkedList(head);
    bool bPalindrome = isPalindrome(head);
    printf("isPalindrome: %d\n", bPalindrome);
    printLinkedList(head);
    delLinkedListNode(head);
    return 0;
}